#ifndef H_C_SKIP_LIST_H
#define H_C_SKIP_LIST_H

#include "../typedefine.h"
#include <exception>
#include <cstring>
#include <random>
#include <chrono>

namespace TB
{
	template<typename T, typename U> class CSkipListNode;
	template<typename T, typename U> class CSkipList;

	template<typename T, typename U>
	class CSkipListLevel
	{
	private:
		friend class CSkipList<T, U>;
		friend class CSkipListNode<T, U>;

	private:
		CSkipListNode<T, U>* m_poNext = nullptr;
		CSkipListNode<T, U>* m_poPrevious = nullptr;
		UINT32 m_dwSpan = 0;
	};

	template<typename T, typename U>
	class CSkipListNode
	{
		NON_COPYABLE(CSkipListNode)
		NON_MOVEABLE(CSkipListNode)
	private:
		CSkipListNode()
		{
		}
		CSkipListNode(const T& key, const U& value) :
			m_oKey(key), m_oValue(value)
		{
		}
		~CSkipListNode()
		{
			SAFE_DELETE_ARRAY(m_poElements);
		}
	public:
		inline UINT8 GetHeight() const { return m_btHeight; }
		inline CSkipList<T, U>* GetOwner() { return m_poOwner; }
		inline const CSkipList<T, U>* GetOwner() const { return m_poOwner; }
		inline const T& GetKey() const { return m_oKey; }
		inline U& GetValue() { return m_oValue; }
		inline const U& GetValue() const { return m_oValue; }
		inline CSkipListNode<T, U>* GetNext()
		{
			return m_btHeight == 0 || m_poOwner == nullptr || m_poElements == nullptr || m_poElements[0].m_poNext == &m_poOwner->m_oTail ? nullptr : m_poElements[0].m_poNext;
		}
		inline CSkipListNode<T, U>* GetPrevious()
		{
			return m_btHeight == 0 || m_poOwner == nullptr || m_poElements == nullptr || m_poElements[0].m_poPrevious == &m_poOwner->m_oHeader ? nullptr : m_poElements[0].m_poPrevious;
		}
		inline const CSkipListNode<T, U>* GetNext() const
		{
			return const_cast<CSkipListNode<T, U>*>(this)->GetNext();
		}
		inline const CSkipListNode<T, U>* GetPrevious() const
		{
			return const_cast<CSkipListNode<T, U>*>(this)->GetPrevious();
		}

		UINT32 CalcRank()
		{
			if (m_poOwner == nullptr)
				throw std::runtime_error("Owner is null");
			if (m_poElements == nullptr || m_btHeight == 0)
				throw std::runtime_error("No data");
			UINT32 dwRank = 0;
			for (auto oNode = this; oNode != &m_poOwner.m_oHeader; oNode = oNode.m_poElements[oNode.m_btHeight - 1].Previous)
			{
				dwRank += oNode.Elements[oNode.m_btHeight - 1].Span;
			}
			return dwRank - 1;
		}

	private:
		void _Reserve(UINT8 btHeight)
		{
			if (m_btHeight >= btHeight)
				return;
			CSkipListLevel<T, U>* poOld = m_poElements;
			UINT8 btOldHeight = m_btHeight;
			m_btHeight = btHeight;
			m_poElements = new CSkipListLevel<T, U>[m_btHeight];
			if (poOld != nullptr)
			{
				memmove(m_poElements, poOld, btOldHeight);
				SAFE_DELETE_ARRAY(poOld);
			}
		}

	private:
		friend class CSkipList<T, U>;
		UINT8 m_btHeight = 0;
		CSkipListLevel<T, U>* m_poElements = nullptr;
		CSkipList<T, U>* m_poOwner = nullptr;
		T m_oKey;
		U m_oValue;
	};

	template<typename T, typename U>
	class CSkipList
	{
		NON_COPYABLE(CSkipList)
		NON_MOVEABLE(CSkipList)
	public:
		CSkipList()
		{
			m_oHeader.m_poOwner = this;
			m_oTail.m_poOwner = this;
		}
		inline CSkipListNode<T, U>* GetFirst() { return m_oHeader.GetNext(); }
		inline const CSkipListNode<T, U>* GetFirst() const { return m_oHeader.GetNext(); }
		inline CSkipListNode<T, U>* GetLast() { return m_oTail.GetPrevious(); }
		inline const CSkipListNode<T, U>* GetLast() const { return m_oTail.GetPrevious(); }
		inline UINT32 GetSize() const { return m_dwSize; }
		inline UINT8 GetHeight() const { return m_btHeight; }

		U& operator[](const T& oKey)
		{
			INT32 dwRank = 0;
			auto node = TryGetLessOrEqual(oKey, dwRank);
			if (node == nullptr)
				node = &m_oHeader;
			else if (node->GetKey() == oKey)
				return node->GetValue();
			auto poNewNode = new CSkipListNode<T, U>(oKey, U());
			_InsertAfter(node, poNewNode);
			return poNewNode->GetValue();
		}

		inline const CSkipListNode<T, U>* TryGet(const T& oKey) const
		{
			return const_cast<CSkipList<T, U>*>(this)->TryGet(oKey);
		}

		inline CSkipListNode<T, U>* TryGet(const T& oKey)
		{
			UINT32 dwRank = 0;
			return TryGet(oKey, dwRank);
		}

		inline const CSkipListNode<T, U>* TryGet(const T& oKey, UINT32& dwRank) const
		{
			return const_cast<CSkipList<T, U>*>(this)->TryGet(oKey, dwRank);
		}

		CSkipListNode<T, U>* TryGet(const T& oKey, UINT32& dwRank)
		{
			auto oRet = TryGetGreaterOrEqual(oKey, dwRank);
			if (oRet != nullptr && oRet.Key == oKey)
				return oRet;
			return nullptr;
		}

		CSkipListNode<T, U>* TryGetGreaterOrEqual(const T& oKey, INT32& dwRank)
		{
			if (m_dwSize == 0)
			{
				dwRank = -1;
				return nullptr;
			}
			dwRank = 0;
			INT8 btLevel = (INT8)m_btHeight - 1;
			CSkipListNode<T, U>* poPrevNode = &m_oHeader;
			CSkipListNode<T, U>* poNode = poPrevNode->m_poElements[btLevel].m_poNext;
			while (btLevel >= 0)
			{
				while (&m_oTail == poNode)
				{
					if (--btLevel < 0)
					{
						dwRank = -1;
						return nullptr;
					}
					poNode = poPrevNode->m_poElements[btLevel].m_poNext;
				}
				if (oKey == poNode->GetKey())
				{
					dwRank += poNode->m_poElements[btLevel].m_dwSpan - 1;
					return poNode;
				}
				if (oKey > poNode->GetKey())
				{
					dwRank += poNode->m_poElements[btLevel].m_dwSpan;
					poPrevNode = poNode;
					poNode = poNode->m_poElements[btLevel].m_poNext;
					continue;
				}
				auto tmp = poNode;
				do
				{
					if (--btLevel < 0)
						return poNode;
					poNode = poPrevNode->m_poElements[btLevel].m_poNext;
				} while (tmp == poNode);
			}
			dwRank = -1;
			return nullptr;
		}

		CSkipListNode<T, U>* TryGetGreater(const T& oKey, INT32& dwRank)
		{
			CSkipListNode<T, U>* poRet = TryGetGreaterOrEqual(oKey, dwRank);
			if (poRet == nullptr)
				return nullptr;
			if (poRet != nullptr && poRet->GetKey() == oKey)
			{
				if (poRet->GetNext() == nullptr)
					dwRank = -1;
				else
					++dwRank;
				return poRet->GetNext();
			}
			return poRet;
		}

		CSkipListNode<T, U>* TryGetLessOrEqual(const T& oKey, INT32& dwRank)
		{
			CSkipListNode<T, U>* poRet = TryGetGreater(oKey, dwRank);
			if (poRet == nullptr)
			{
				dwRank = (INT32)GetSize() - 1;
				return GetLast();
			}
			return poRet->GetPrevious();
		}

		CSkipListNode<T, U>* TryGetLess(const T& oKey, INT32& dwRank)
		{
			CSkipListNode<T, U>* poRet = TryGetGreaterOrEqual(oKey, dwRank);
			if (poRet == nullptr)
			{
				dwRank = (INT32)GetSize() - 1;
				return GetLast();
			}
			return poRet->GetPrevious();
		}

		CSkipListNode<T, U>* GetByRank(INT32& dwRank)
		{
			if (dwRank < 0)
				dwRank = (INT32)m_dwSize + dwRank;
			if (dwRank < 0 || dwRank >= (INT32)m_dwSize)
				return nullptr;
			if (m_btHeight == 0)
				return nullptr;
			UINT32 dwExpectSpan = dwRank + 1;
			UINT32 dwSpan = 0;
			INT8 btLevel = (INT8)m_btHeight - 1;
			CSkipListNode<T, U>* poNode = &m_oHeader;
			CSkipListNode<T, U>* poRet = nullptr;
			while (btLevel >= 0)
			{
				if (poNode == &m_oTail)
				{
					poRet = nullptr;
					break;
				}
				UINT32 dwNextSpan = dwSpan + poNode->m_poElements[btLevel].m_poNext->m_poElements[btLevel].m_dwSpan;
				if (dwNextSpan == dwExpectSpan)
				{
					poRet = poNode->m_poElements[btLevel].m_poNext;
					break;
				}
				if (dwNextSpan < dwExpectSpan)
				{
					dwSpan = dwNextSpan;
					poNode = poNode->m_poElements[btLevel].m_poNext;
					continue;
				}
				--btLevel;
			}
			return poRet == &m_oTail ? nullptr : poRet;
		}

		bool Remove(const T& oKey)
		{
			auto poNode = TryGet(oKey);
			return Remove(poNode);
		}

		bool Remove(CSkipListNode<T, U>* poNode, bool bDestroy = true)
		{
			if (poNode->GetOwner() != this || poNode == &m_oHeader || poNode == &m_oTail)
				return false;
			--m_dwSize;
			poNode->m_poOwner = nullptr;
			CSkipListNode<T, U>* poNext = nullptr;
			UINT8 btLevel = 0;
			// �������ýڵ�
			for (; btLevel < poNode->m_btHeight; ++btLevel)
			{
				CSkipListLevel<T, U>& roNodeLevel = poNode->m_poElements[btLevel];
				poNext = roNodeLevel.m_poNext;
				poNext->m_poElements[btLevel].m_dwSpan += roNodeLevel.m_dwSpan - 1;
				CSkipListNode<T, U>* poPrev = roNodeLevel.m_poPrevious;
				poNext->m_poElements[btLevel].m_poPrevious = poPrev;
				poPrev->m_poElements[btLevel].m_poNext = poNext;
				roNodeLevel.m_poNext = nullptr;
				roNodeLevel.m_poPrevious = nullptr;
			}
			// ������Խ�Լ��Ľڵ�
			for (; btLevel < m_btHeight; ++btLevel)
			{
				while (poNext != nullptr && btLevel >= poNext->m_btHeight)
					poNext = poNext->m_poElements[btLevel - 1].m_poNext;
				if (poNext == nullptr)
					break;
				--poNext->m_poElements[btLevel].m_dwSpan;
			}
			if (bDestroy)
				delete poNode;
			return true;
		}

		std::pair<CSkipListNode<T, U>*, bool> InsertIfNotExist(const T& oKey, const U& oValue)
		{
			CSkipListNode<T, U>* poPrevNode = TryGetLessOrEqual(oKey);
			if (poPrevNode != nullptr && poPrevNode->GetKey() == oKey)
				return std::make_pair(poPrevNode, false);
			if (poPrevNode == nullptr)
				poPrevNode = &m_oHeader;
			auto poNode = new CSkipListNode<T, U>(oKey, oValue);
			_InsertAfter(poPrevNode, poNode);
			return std::make_pair(poNode, true);
		}

		CSkipListNode<T, U>* InsertIfNotExist(CSkipListNode<T, U>* poNode)
		{
			if (poNode == nullptr)
				return nullptr;
			if (poNode->m_poOwner == this)
				return poNode;
			if (poNode->m_poOwner != nullptr)
				throw std::runtime_error("node already in another skiplist");
			CSkipListNode<T, U>* poPrevNode = TryGetLessOrEqual(poNode->GetKey());
			if (poPrevNode != nullptr && poPrevNode->GetKey() == poNode->GetKey())
				return poPrevNode;
			if (poPrevNode == nullptr)
				poPrevNode = &m_oHeader;
			_InsertAfter(poPrevNode, poNode);
			return poNode;
		}

		void Clear()
		{
			if (m_btHeight != 0)
			{
				while (m_oHeader.m_poElements[0].m_poNext != &m_oTail)
				{
					CSkipListNode<T, U>* poNext = m_oHeader.m_poElements[0].m_poNext;
					m_oHeader.m_poElements[0].m_poNext = poNext->m_poElements[0].m_poNext;
					delete poNext;
				}
			}
			for (UINT8 i = 0; i != m_btHeight; ++i)
			{
				m_oHeader.m_poElements[i].m_poNext = &m_oTail;
				m_oTail.m_poElements[i].m_poPrevious = &m_oHeader;
				m_oTail.m_poElements[i].m_dwSpan = 1;
			}
			m_btHeight = 0;
			m_dwSize = 0;
		}

	private:
		void _InsertAfter(CSkipListNode<T, U>* poPrevNode, CSkipListNode<T, U>* poNewNode)
		{
			poNewNode->m_poOwner = this;
			UINT8 btLevelCount = poNewNode->m_btHeight;
			if (btLevelCount == 0)
			{
				if (m_dwSize < 5)
					btLevelCount = 1;
				else
				{
					UINT32 dwRand = m_oRandom();
					btLevelCount = (UINT8)_TrailingZeroCount(~dwRand) + 1;
				}
				poNewNode->m_poElements = new CSkipListLevel<T, U>[btLevelCount];
				poNewNode->m_btHeight = btLevelCount;
			}
			if (m_oHeader.m_btHeight < btLevelCount)
			{
				UINT8 btCapacity = _Fix(btLevelCount);
				m_oHeader._Reserve(btCapacity);
				m_oTail._Reserve(btCapacity);
			}
			for (; m_btHeight < btLevelCount; ++m_btHeight)
			{
				m_oHeader.m_poElements[m_btHeight].m_poNext = &m_oTail;
				m_oTail.m_poElements[m_btHeight].m_poPrevious = &m_oHeader;
				m_oTail.m_poElements[m_btHeight].m_dwSpan = m_dwSize + 1;
			}
			CSkipListNode<T, U>* poNode = poPrevNode;
			UINT32 dwOffset = 0;
			for (UINT8 i = 0; i != m_btHeight; ++i)
			{
				while (i >= poNode->m_btHeight)
				{
					dwOffset += poNode->m_poElements[i - 1].m_dwSpan;
					poNode = poNode->m_poElements[i - 1].m_poPrevious;
				}
				CSkipListLevel<T, U>& roPrevNodeLevel = poNode->m_poElements[i];
				CSkipListLevel<T, U>& roNextNodeLevel = roPrevNodeLevel.m_poNext->m_poElements[i];
				if (i >= btLevelCount)
				{
					// ������Խ�Լ��Ľڵ�
					++roNextNodeLevel.m_dwSpan;
					continue;
				}
				CSkipListLevel<T, U>& roNewNodeLevel = poNewNode->m_poElements[i];
				roNewNodeLevel.m_dwSpan = dwOffset + 1;
				roNextNodeLevel.m_dwSpan = roNextNodeLevel.m_dwSpan + 1 - roNewNodeLevel.m_dwSpan;
				roNewNodeLevel.m_poNext = roPrevNodeLevel.m_poNext;
				roNewNodeLevel.m_poPrevious = poNode;
				roPrevNodeLevel.m_poNext = poNewNode;
				roNextNodeLevel.m_poPrevious = poNewNode;
			}
			++m_dwSize;
		}

		inline UINT8 _Fix(UINT8 btCapacity)
		{
			btCapacity -= 1;
			btCapacity |= btCapacity >> 1;
			btCapacity |= btCapacity >> 2;
			btCapacity |= btCapacity >> 4;
			btCapacity += 1;
			return btCapacity;
		}

		inline UINT32 _TrailingZeroCount(UINT32 x)
		{
			x = (x & (UINT32)(-(INT32)x)) - 1;
			x -= (x >> 1) & 0x55555555;
			x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
			x = ((x >> 4) + x) & 0x0f0f0f0f;
			x += x >> 8;
			x += x >> 16;
			return x & 0x0000003f;
		}

	private:
		friend class CSkipListNode<T, U>;
		thread_local static std::linear_congruential_engine<uint_fast32_t, 48271, 1, 2147483648> m_oRandom;
		CSkipListNode<T, U> m_oHeader;
		CSkipListNode<T, U> m_oTail;
		UINT8 m_btHeight = 0;
		UINT32 m_dwSize = 0;
	};

	template<typename T, typename U> thread_local std::linear_congruential_engine<uint_fast32_t, 48271, 1, 2147483648> CSkipList<T, U>::m_oRandom((UINT32)std::chrono::system_clock::now().time_since_epoch().count());
}

#endif
